Polygon meshes are widely used in computer aided geometric design, geometric modeling, medical imaging, and computer graphics to represent surfaces in digital form. Polygon meshes are described in detail in U.S. Pat. No. 5,506,947 “Curve and Surface Smoothing Without Shrinkage,” by G. Taubin, and in the paper “A Signal Processing Approach To Fair Surface Design,” by G. Taubin, Siggraph'95 Conference Proceedings, August 1995, pages 351-358, both are incorporated herein by reference in its entirety for all purposes. A polygon mesh includes a polygon mesh connectivity, a set of polygon mesh vertex positions, and a set of polygon mesh normals. The polygon mesh connectivity includes a plurality of vertices, and a plurality of faces. The set of polygon mesh vertex positions includes a plurality of vertex position vectors, with each vertex position vector corresponding to one vertex of the polygon mesh connectivity. The set of polygon mesh normals can be either a set of polygon mesh vertex normals or a set of polygon mesh face normals. The set of polygon mesh vertex normals includes either a plurality of vertex normals, with each vertex normal corresponding to one vertex of the polygon mesh connectivity. The set of polygon mesh face normals includes either a plurality of face normals, with each face normal corresponding to one face of the polygon mesh connectivity.
An isosurface extraction algorithm constructs a polygon mesh approximation of a level.set of a scalar function defined in the volume spanned by a 3D regular grid. Data acquired by medical imaging systems such as Computed Axial Tomography (CAT) Scanners and Magnetic Resonance Imaging (MRI) Scanners are example of scalar functions defined on the vertices of a 3D regular grid. The 3D regular grid includes a plurality of grid vertices and a plurality of grid edges, with each grid edge connecting two particular grid vertices. Two grid vertices connected by a grid edge are called neighbors. The grid vertices of the 3D regular grid are points Pα in 3D space, where α=(α0,α1,α2) is a triple of non-negative integers, α0ε{0, . . . , n0−1}, α1ε{0, . . . , n1−1}, α2ε{0, . . . , n2−1}. FIG. 1 is a prior art diagram showing a 3D regular grid 100 and one of its cells 140. The grid vertices of the 3D regular grid are organized as n0 layers 110, n1 rows 120, and n2 columns 130. Each set of eight neighboring grid vertices form a cell 140Cα={Pα·Pα−(001)·Pα−(010)·Pα−(011)·Pα−(110)·Pα−(111)}
The cells of the 3D regular grid correspond to values of α=(α0, α1, α2) in the following ranges: αnε{1, . . . , n0−1}, α1ε{1, . . . , n1−1}, α2ε{1, . . . , n2−1}. The vertices of cell 140 are grid vertices 141, 142, 143, 144, 145, 146, 147, and 148.
The scalar function ƒ(P) is specified by its values fα=f(Pα) on the grid vertices Pα of a 3D regular grid, and by a method to interpolate in between these values. The level set is specified by an isovalue f0. The interpolation scheme is assumed to be linear along the grid edges, so that the isosurface cuts each edge in no more than one point. IfPα and Pα−δ1 are grid points connected by an edge, andfα>f0>fα−δ1 or fα<f0<fα−δ1,the location of the point Pα,j where the isosurface intersects the edge is given by the formula
      p          α      ,      j        =                              (                      1            -                          t                              α                ,                j                                              )                ⁢                  p          β                    +                        t                      α            ,            j                          ⁢                  p          α                ⁢                                  ⁢        where        ⁢                                  ⁢                  t                      α            ,            j                                =                            f          β                -                  f          0                                      f          β                -                  f          α                    
The isosurface extraction algorithm determines interfaces between adjacent data values indicating a change in the measured value, and then models the surface with polygonal elements having a vertex position for each polygon mesh vertex, and a vector normal to the surface at each of the vertices, or a face normal to the surface at each polygonal face of the polygon mesh. The most popular isosurface algorithms are Cuberille, described by L. S. Chen, G. T. Herman, R. A. Reynolds, and J. K. Udupa in the paper “Surface Shading in the Cuberille Environment,” IEEE Computer Graphics and Applications, vol. 5, no. 12, pages 33-42, 1985; and Marching Cubes, described in detail in U.S. Pat. No. 5,166,876 “System and Method for Detecting Internal Structures Contained Within the Interior Region of a Solid Object,” by H. E. Cline and W. E. Lorensen, and in the paper “Marching Cubes: a High Resolution 3D Surface Construction Algorithm,” Siggraph Conference Proceedings, 1987, by W. E. Lorensen and A. V. Cline. In this disclosure we refer to the polygon meshes produced by these and related algorithms as isosurface meshes.
In the Marching Cubes method mentioned above the points defined by the intersection of the isosurface with the grid edges are the vertices of the polygon mesh. In the Cuberille method mentioned above each of the points defined by the intersection of the isosurface with the grid edges correspond to one polygon mesh face. In his PhD thesis “Segmentation and Surface-Based Modeling of Objects in Three-Dimensional Biomedical Images,” New York University, New York, March 1991, A. D. Kalvin observed that the polygon mesh generated by Marching Cubes is the dual mesh of the quadrilateral mesh generated by the Cuberille algorithm. Each vertex of the grid where the scalar function is specified (the primal grid) is the centroid of a dual grid cell, or voxel. Every edge of the primal grid intersects the common face of the two voxels corresponding to the ends of the edge. The mesh generated by the Cuberille algorithm is the regularized (converted to manifold) boundary surface of the solid defined by the set of voxels corresponding to grid vertices with scalar value above the isovalue. Without regularization, in general this mesh is highly singular (non-manifold). The conversion to manifold requires duplication of vertices and edges, so that in the resulting mesh every edge has exactly two incident faces. Which vertices to duplicate and how to connect the faces can be determined by virtually {\em shrinking} the solid, moving the faces in the direction of the inside. The multiplicity of each dual grid vertex in the regularized mesh only depends on the local connectivity of the eight incident voxels. Again, the regularization can be done by table lookup while the volume data is being scanned, with a table of size 256.
The vertices of the polygon mesh generated by the Marching Cubes method are connected forming polygon faces according to the following procedure. Since the function value associated with each of the eight corners of a cell may be either above or below the isovalue (isovalues equal to grid function values are called singular and should be avoided), there are 256 possible configurations. A polygonization of the vertices within each cell for each one of these configurations is stored in a static lookup table. When symmetries are taken into account, the size of the table can be reduced quite significantly.
The Cuberille algorithm constructs its isosurface mesh from the same information as the Marching Cubes algorithm. The edge intersections in the primal mesh specify the location of the face centroids of the Cuberille mesh. The location of the cuberille vertices can then be computed by local averaging, or by using more accurate schemes, such as those introduced by S. Gibson in the paper “Constrained Elastic Surface Nets: Generating Smooth Surfaces From Binary Segmented Data,” Medical Image Computation and Computer Assisted Interventions, Conference Proceedings, pages 888-898, 1998; and by G. Taubin in the paper “Dual Mesh Resampling,” Pacific Graphics 2001, Conference Proceedings, Tokyo, Japan, October 2001. The situation is similar for normals. If computed in the server as the gradient of the scalar function at the edge intersection points, and included in the compressed data, the Marching Cubes decoder will treat them as vertex normals, and the Cuberille decoder as face normals. T. Moller, R. Machiraju, K. Muller, and R. Yagel discuss different methods to estimate isosurface normals from volume data in the paper “A Comparison of Normal Estimation Schemes,” IEEE Visualization'97, Conference Proceedings, pages 19-26, 1997. If the normals are not included in the compressed data, then it is up to the client to decide how to estimate them from the vertex coordinates and the connectivity information. The implication of these observations is that there is considerable freedom in the implementation of the decoder, making absolutely no changes to the encoder or the compressed bitstream. It is not even necessary for the decoder to produce a polygon mesh as output. For visualization purposes, and in particular if normals are included in the compressed data, a point-based approach could be very effective. One such point based surface representation approach is described by S. Rusinkiewicz and M. Levoy in the paper “Qsplat: A Multiresolution Point Rendering System for Large Meshes,” Siggraph Conference Proceedings, 2000. Another related method is described in U.S. Pat. No. 4,719,685 “Dividing Cubes System And Method For The Display Of Surface Structures Contained Within The Interior Region of a Solid Body,” by H. E. Cline, W. E. Lorensen, and S. Ludke.
A number of general purpose polygon mesh compression algorithms have been proposed in recent years. M. F. Deering developed a mesh compression scheme for hardware acceleration, described in U.S. Pat. No. 5,793,371 “Method and apparatus for geometric compression of three-dimensional graphics data,” and U.S. Pat. No. 5,842,004 “Method and apparatus for decompression of compressed geometric three-dimensional graphics data.” Other methods to encode the connectivity of triangle meshes with no loss of information were introduced by Taubin and Rossignac in U.S. Pat. No. 5,825,369 “Compression of Simple Geometric Models Using Spanning Trees,” and U.S. Pat. No. 5,905,507 “Compression of Geometric Models Using Spanning Trees;” C. Touma and C. Gotsman in U.S. Pat. No. 6,167,159 “Triangle Mesh Compression;” J. Rossignac in the paper “Edgebreaker: Connectivity Compression for Triangular Meshes,” IEEE Transactions on Visualization and Computer Graphics, vol. 5, no. 1, pp. 47-61, January-March 1999; S. Gumhold in U.S. Pat. No. 6,469,701 “Method for Compressing Graphical Information;” and others.
In the Technical Report GIT-GVU-99-36, “Connectivity Compression for Irregular Quadrilateral Meshes,” Georgia Tech GVU, 1999, A. King, D. Szymczak and J. Rossignac describe a method to compress quadrilateral meshes. Methods to encode the connectivity of polygon meshes composed of faces with arbitrary number of corners were introduced by M. Isenburg and J. Snoeyink in the paper “Face fixer: Compressing Polygon Meshes with Properties,” Siggraph 2000 Conference Proceedings, pages 263-270, July 2000; B. Konrod and C. Gotsman in the paper “Efficient Coding of Non-Triangular Meshes,” Pacific Graphics Conference Proceedings, Hong-Kong, 2000; and A. Khodakovsky, P. Alliez, M. Desbrun, and P. Schroder in the paper “Near-Optimal Connectivity Encoding of 2-Manifold Polygon Meshes,” Graphical Models, Special Issue on Processing of Large Polygonal Meshes, 2003. These algorithms focus on compressing the connectivity information very efficiently, and are all based on a traversal of the primal or dual graph of the mesh. Some of them compress connectivity of very regular meshes to a small fraction of a bit per vertex, and all to 2-4 bits per vertex in the worst case. When the geometry information (vertex coordinates, and optionally normals, colors, and texture coordinates) is also taken into account, the cost per vertex increases considerably. For example, adding only vertex coordinates quantized to 10 bits per vertex lifts the cost to typically 8-16 bits per vertex. In addition, all of these approaches are incompatible with the out-of-core nature of isosurface extraction algorithms that visit the voxels in scan order.
In the paper “Progressive Geometry Compression,” Siggraph 2000 Conference Proceedings, pages 271-278, July 2000, A. Khodakovsky, P. Schroder, and W. Sweldens follow a different approach to compress large connected and uniformly sampled meshes of low topological complexity, based on resampling, subdivision and wavelets. They obtain up to one order of magnitude better compression rates than with the connectivity preserving schemes, by approximating the mesh geometry with a subdivision mesh, and compressing this mesh instead.
In the paper “Semi-Regular Mesh Extraction From Volumes,” IEEE Visualization 2000, Conference Proceedings, pages 275-282, October 2000, Z. J. Wood, M. Desbrun, P. Schroder, and D. Breen introduced a method based on surface wave propagation to extract isosurfaces from distance volumes that produces semi-regular multi-resolution meshes. These meshes can be compressed with Khodakovsky's wavelet-based scheme.
Isosurface algorithms generally, take as input very large volume data files, and produce polygon meshes with very large number of vertices and faces. Data stored in a server can be transmitted to a client for remote visualization. The server can store and transmit the volume data to the client, which then executes the isosurface algorithm on the received volume data, and renders the resulting polygon mesh in a visualization system. Alternatively, the server can compute the isosurface and transmit the resulting polygon mesh to the client, which only renders the received polygon mesh in a visualization system.
In both cases the transmission time constitutes a major bottleneck because of the large file sizes involved. In the first case, in addition to the size of the transmitted data, the burden of the computation is shifted to the client. In the second case this is true even using general purpose polygon mesh compression schemes to reduce the size of the transmitted data. It is, therefore, important to compress the data stored in the server and/or transmitted to a remote client, and to be able to divide the computational burden between server and client according to the computational resources of the client.
All isosurface construction algorithms construct an isosurface approximation from an occupancy image, a set of intersection points, and a set of intersection point surface normals. The occupancy image, the set of intersection points, and the set of intersection point surface normals are extracted from the volume data. Since whether a grid edge intersects the isosurface or not depends on the values of the scalar function at the grid edge ends, isosurface construction algorithms generate polygon mesh vertices an faces as a function of an “occupancy image” extracted from the volume data. The occupancy image is a 3D binary image defined by one grid vertex bit per grid vertexB={bα:α=(α0,α1,α2)} where bαε{0,1},specifying whether the scalar function attains a value above or below the isovalue on that grid vertex. The location of the surface points along the intersecting grid edges and the polygon mesh normals are associated with the intersecting grid edges. A grid edge is an intersecting grid edge if occupancy image has different values at the grid edge ends. Since the gradient vector of a function is normal to its level sets, normals used for shading can optionally be computed during the volume traversal as finite difference approximations to the gradient vectors normalized to unit length.
FIG. 2 is a flow chart of a typical prior art isosurface extraction algorithm 210 which takes volume data 205 as input and produces surface data 220 as output. While the isosurface extraction algorithm 210 scans the volume data in step 215, it determines the occupancy image in step 230, computes the intersection points in step 235, computes normal vectors to the intersection points in step 240, and from the information contained in the occupancy image, intersection points, and normal vectors, in step 245 it computes a surface representation that returns as the surface data 220.
FIG. 3 is a prior art diagram that shows the occupancy image 300 composed of grid vertex bits 310, each grid vertex bit 310 corresponding to a grid vertex 320, each grid vertex 320 having an associated scalar function value 330, the value of the grid vertex bit 310 being determined by whether the associated scalar function value 330 is greater than the isovalue 340. In this diagram each grid points 320 corresponds to a voxel 350 as in the Cuberille algorithm. The occupancy image partitions the voxels into two sets 360 and 370. The topology and connectivity of the isosurface 370 is determined by the set of voxel faces separating the sets 360 and 370.
FIG. 4 is a prior art diagram that shows the intersection points. Each intersection point 410 corresponds to one quadrilateral face 420 separating the sets 360 and 370 of FIG. 3.
FIG. 5 is a prior art diagram that shows the normal vectors. Each normal vector 520 corresponds to one intersection point 510.
In the paper “Compression of Isosurfaces,” Proceedings of IEEE Vision, Modeling and Visualization (VMV 2001), Stuttgart, Germany, November 2001, D. Saupe and J.-P. Kuska presented an algorithm to compress isosurfaces, which extracts and encodes the occupancy image and intersection points. Normals are computed from the reconstructed Marching Cubes polygon mesh. The occupancy image is encoded with an octree-based scheme to deal more efficiently with large homogeneous regions of empty space. The intersection points are encoded with a multi-symbol context-based arithmetic coder. This is a complex method with compression rates significantly higher than those achieved using this invention. In the paper “Space-Efficient Boundary Representation of Volumetric Objects,” Proceedings of the Joint Eurographics-IEEE TCVG Symposium on Visualization (VisSym01), Ascona, Switzerland, May 2001, L. Mroz and H. Hauser encode the occupancy image using a more complex scheme based on chain coding, where the voxels that contain isosurface intersections are linked in long chains and represented as a sequence of symbols, each one specifying in which direction to go to visit the next cell. This method is also significantly less efficient than this invention, even if normals are not included in the compressed data. In the paper “Compressing Isosurfaces Generated with Marching Cubes,” The Visual Computer, vol. 18, no. 1, pages 54-67, 2002, S. N. Yang and T. S. Wu describe a rather complex method to compress triangle meshes generated by the Marching Cubes algorithm. Each mesh vertex is represented by the index of the containing cube, the index of the supporting edge, and the position of the vertex along the supporting edge. The decoder interconnects these vertices forming triangles using the occupancy image, as in the original Marching Cubes method. But the occupancy image is not encoded in the bitstream. Instead, it is reconstructed from the cube and edge indices in the encoding of mesh vertices by a complex procedure that in fact determines the connected components of the grid graph after removing the edges where mesh vertices are supported. Normal vectors are not compressed. Compression rates are several times worse than with the method of this invention, and it is not possible to do an out-of-core implementation.
Entropy encoding is a well established technique to represent with a minimum number of bits a finite sequence of “independent symbols” that belong to a finite “alphabet”. The fundamentals of entropy encoding is explained by D. Salomon in the book “Data Compression: The Complete Reference,” Springer-Verlag, 1997, ISBN 0-387-98280-9. Symbols that appear more often in the sequence are represented with fewer bits than those that appear more infrequently. The absolute lower bound for the total number of bits necessary to represent the sequence of independent symbols with no loss of information is given by the so-called “entropy.” In practice the “arithmetic coder,” described by I. H. Witten, R. M. Neal, and J. G Cleary, in the paper “Arithmetic coding for data compression,” Communications of the ACM, vol. 30, no. 6, June 1987, asymptotically achieves the entropy. Arithmetic coding is used as the basis of many image and data compression schemes and applications, such as those described by K. M. Marks, in the paper “A JBIG-ABIC compression engine for digital document processing,” IBM Journal of Research and Development, vol. 42, no. 6, 1998. Arithmetic coding has also been implemented in hardware, as described by M. J. Slattery and J. L. Mitchell, in the paper “The Qx-coder,” IBM Journal of Research and Development, vol. 42, no. 6, 1998.
To deal with the lack of stationary distribution of symbols in the sequence, “adaptive” models are used. In arithmetic coding with an adaptive model the encoder updates the alphabet probabilities after encoding each symbol. Since encoder and decoder must use the same model to encode and decode each symbol, the model update procedure must be based on data previously encoded, and agreed upon information. Among these data are the initial probabilities, which may be hard-coded or included in the compressed data. A common practice is to start with uniform probabilities and keep track of the relative symbol frequencies as probability estimates.
For binary data, where the alphabet is composed of two symbols, keeping track of global symbol frequencies is usually not good enough as a model update procedure, and a “context-based” procedure is used. This is a state machine model with separate sets of probability estimates associated with each state or “context”. The update procedure determines the context from previously encoded data, and after the symbol is encoded with the probabilities associated with a context, the set of probabilities corresponding to that context is updated, but not the other. Context-based arithmetic coding is a very efficient adaptive compression scheme.
JBIG is short for “Joint Bi-level Image experts Group.” This is both the name of a standards committee, and of a particular scheme for the lossless compression of binary images, described in the international standard ITU-T T.82 Information technology—Coded representation of picture and audio information—Progressive bi-level image compression, March 93. It can also be used for coding gray scale and color images with limited numbers of bits per pixel. JBIG is one of the best available schemes for lossless image compression. The JBIG algorithm is based on context-based arithmetic coding. For each pixel in an image a “context” is derived from a specific fixed pattern of surrounding pixels preceding the current pixel in the scan order. The standard defines several such neighborhoods.
FIG. 6 is a prior art diagram showing two different ways 620 and 630 of defining a 10-bit context of a bit 610 described in the JBIG standard. All the above mentioned papers and references are incorporated herein for all purposes.